home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / ui / OGC / runtime.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-06  |  13.3 KB  |  409 lines
  1. /* Copyright 1988 Hans-J. Boehm, Alan J. Demers */
  2. /**
  3.    GRAB Graph Layout and Browser System
  4.  
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8. /*********************************/
  9. /*                               */
  10. /* Definitions for conservative  */
  11. /* collector                     */
  12. /*                               */
  13. /*********************************/
  14.  
  15. /*********************************/
  16. /*                               */
  17. /* Easily changeable parameters  */
  18. /*                               */
  19. /*********************************/
  20.  
  21. #define VAX         /* This is a VAX, as opposed to a SPARC, */
  22.             /* Motorola 68000 or I386.                        */
  23.             /* We assume:  M68K ==> Sun3, I386 ==> Sequent Symmetry */
  24. #define PRINTSTATS  /* Print garbage collection statistics                  */
  25.             /* For less verbose output, undefine in reclaim.c      */
  26.  
  27. #define PRINTTIMES  /* Print the amount of time consumed by each garbage   */
  28.             /* collection.                                         */
  29.  
  30. #ifdef NOSTATS
  31. #undef PRINTSTATS
  32. #undef PRINTTIMES
  33. #endif 
  34.  
  35. #define PRINTBLOCKS /* Print object sizes associated with heap blocks,     */
  36.             /* whether the objects are atomic or composite, and    */
  37.             /* whether or not the block was found to be empty      */
  38.             /* duing the reclaim phase.  Typically generates       */
  39.             /* about one screenful per garbage collection.         */
  40. #undef PRINTBLOCKS
  41.  
  42. #ifdef M68K
  43. #  define UNALIGNED       /* Pointers are not longword aligned         */
  44. #  define ALIGNMENT   2   /* Pointers are aligned on 2 byte boundaries */
  45.               /* by the Sun C compiler.                    */
  46. #else
  47. #  ifdef VAX
  48. #    undef UNALIGNED      /* Pointers are longword aligned by 4.2 C compiler */
  49. #    define ALIGNMENT 4
  50. #  else
  51. #      ifdef SPARC
  52. #        undef UNALIGNED
  53. #        define ALIGNMENT 4
  54. #      else
  55. #        ifdef I386
  56. #           undef UNALIGNED         /* Sequent compiler aligns pointers */
  57. #           define ALIGNMENT 4
  58. #        else
  59.        --> specify alignment <--
  60. #        endif
  61. #      endif
  62. #  endif
  63. # endif
  64.  
  65. # ifdef M68K
  66. #   define STACKTOP ((char *)0xf000000) /* Beginning of stack on a Sun 3 */
  67.                     /* Sun 2 value is 0x1000000      */
  68. # else
  69. #   ifdef VAX
  70. #     define STACKTOP ((char *)0x80000000) /* Beginning of stack under 4.n BSD */
  71. #   else
  72. #       ifdef SPARC
  73. #         define STACKTOP ((char *) 0xf8000000)
  74. #       else
  75. #         ifdef I386
  76. #           define STACKTOP ((char *) 0x3ffff000)  /* For Sequent */
  77. #         else
  78.          --> specify
  79. #         endif
  80. #       endif
  81. #   endif
  82. # endif
  83.  
  84. /* Start of data segment for each of the above systems.  Note that the */
  85. /* default case works only for contiguous text and data, such as on a  */
  86. /* Vax.                                                                */
  87. # ifdef M68K
  88. #   define DATASTART ((char *)((((long) (&etext)) + 0x1ffff) & ~0x1ffff))
  89. # else
  90. #     ifdef I386
  91. #       define DATASTART ((char *)((((long) (&etext)) + 0xfff) & ~0xfff))
  92. #     else
  93. #       define DATASTART (&etext)
  94. #     endif
  95. # endif
  96.  
  97. # define HINCR 16          /* Initial heap increment, in blocks of 4K        */
  98. # define HINCR_MULT 3      /* After each new allocation, hincr is multiplied */
  99. # define HINCR_DIV 2       /* by HINCR_MULT/HINCR_DIV                        */
  100. # define GC_MULT 3         /* Don't collect if the fraction of   */
  101.                /* non-collectable memory in the heap */
  102.                /* exceeds GC_MUL/GC_DIV              */
  103. # define GC_DIV  4
  104.  
  105. # define NON_GC_HINCR 8    /* Heap increment if most of heap if collection */
  106.                /* was suppressed because most of heap is not   */
  107.                /* collectable                                  */
  108.  
  109. /*  heap address bounds.  These are extreme bounds used for sanity checks. */
  110. /*  HEAPLIM may have to be increased for machines with incredibly large    */
  111. /*  amounts of memory.                                                     */
  112.  
  113. # ifdef M68K
  114. #   define HEAPSTART 0x00010000
  115. #   define HEAPLIM   0x04000000
  116. # else
  117. #   ifdef SPARC
  118. #       define HEAPSTART 0x00010000
  119. #       define HEAPLIM   0x10000000
  120. #   else
  121. #     ifdef VAX
  122. #       define HEAPSTART 0x400
  123. #       define HEAPLIM   0x10000000
  124. #     else
  125. #       ifdef I386
  126. #         define HEAPSTART 0x1000
  127. #         define HEAPLIM 0x10000000
  128. #       else
  129.        --> values unknown <--
  130. #       endif
  131. #     endif
  132. #   endif
  133. # endif
  134.  
  135. /*********************************/
  136. /*                               */
  137. /* Machine-dependent defines     */
  138. /*                               */
  139. /*********************************/
  140.  
  141. #define WORDS_TO_BYTES(x)   (((int)(x))<<2)
  142. #define BYTES_TO_WORDS(x)   (((int)(x))>>2)
  143.  
  144. #define WORDSZ              32
  145. #define LOGWL               5    /* log[2] of above */
  146. #define BYTES_PER_WORD      (sizeof (word))
  147. #define NREGS               16
  148. #define ONES                0xffffffff
  149. #define MSBYTE              0xff000000
  150. #define SIGNB               0x80000000
  151. #define MAXSHORT            0x7fff
  152. #define modHALFWORDSZ(n) ((n) & 0xf)    /* mod n by size of half word    */
  153. #define divHALFWORDSZ(n) ((n) >> 4)    /* divide n by size of half word */
  154. #define modWORDSZ(n) ((n) & 0x1f)       /* mod n by size of word         */
  155. #define divWORDSZ(n) ((n) >> 5)         /* divide n by size of word      */
  156. #define twice(n) ((n) << 1)             /* double n                      */
  157.  
  158. typedef unsigned long word;
  159.  
  160. #define TRUE  1
  161. #define FALSE 0
  162.  
  163. /*********************/
  164. /*                   */
  165. /*  Size Parameters  */
  166. /*                   */
  167. /*********************/
  168.  
  169. /*  heap block size, bytes */
  170. /* for RT see comment below */
  171.  
  172. #define HBLKSIZE   0x1000
  173.  
  174.  
  175. /*  max size objects supported by freelist (larger objects may be   */
  176. /*  allocated, but less efficiently)                                */
  177. /*      asm(".set MAXOBJSZ,0x200")      if HBLKSIZE/2 == 0x200          */
  178.  
  179. #define MAXOBJSZ    BYTES_TO_WORDS(HBLKSIZE/2)
  180. #define MAXAOBJSZ   BYTES_TO_WORDS(HBLKSIZE/2)
  181.  
  182. # define divHBLKSZ(n) ((n) >> 12)
  183.  
  184. # define modHBLKSZ(n) ((n) & 0xfff)
  185.  
  186. # define HBLKPTR(objptr) ((struct hblk *)(((long) (objptr)) & ~0xfff))
  187.  
  188. # define MAXHBLKS 4000      /* Maximum number of chunks which can be */
  189.                  /* allocated                             */
  190.  
  191.  
  192. /********************************************/
  193. /*                                          */
  194. /*    H e a p   B l o c k s                 */
  195. /*                                          */
  196. /********************************************/
  197.  
  198. /*  heap block header */
  199. #define HBLKMASK   (HBLKSIZE-1)
  200.  
  201. #define BITS_PER_HBLK (HBLKSIZE * 8)
  202.  
  203. #define MARK_BITS_PER_HBLK (BITS_PER_HBLK/WORDSZ)
  204.        /* upper bound                                    */
  205.        /* We allocate 1 bit/word.  Only the first word   */
  206.        /* in each object is actually marked.             */
  207.  
  208. # define MARK_BITS_SZ ((MARK_BITS_PER_HBLK + WORDSZ - 1)/WORDSZ)
  209.        /* Upper bound on number of mark words per heap block  */
  210.  
  211. struct hblkhdr {
  212.     int hbh_sz;     /* sz > 0 ==> objects are sz-tuples of poss. pointers */
  213.             /* sz < 0 ==> objects are sz-tuples not pointers      */
  214.             /* if free, the size in bytes of the whole block      */
  215.             /* Misc.c knows that hbh_sz comes first.              */
  216.     struct hblk ** hbh_index;   /* Pointer to heap block list entry   */
  217.                 /* for this block                     */
  218.     struct hblk * hbh_next; /* Link field for hblk free list */
  219.     long hbh_mask;      /* If hbh_mask >= 0 then:                          */
  220.             /*   x % (4 * hbh_sz) == x & hbh_mask              */
  221.             /*   sz is a power of 2 and < the size of a heap   */
  222.             /*     block.                                      */
  223.             /* A hack to speed up pointer validity check on    */
  224.             /* machines with slow division.                    */
  225.     long hbh_marks[MARK_BITS_SZ];
  226.                 /* Bits 2i and 2i+1 in the array refer to the   */
  227.                 /* object starting at the ith word (header      */
  228.                 /* INCLUDED) in the heap block.                 */
  229.                 /* For free blocks, hbh_marks[0] = 1, indicates */
  230.                 /* block is uninitialized.                      */
  231. };
  232.  
  233. /*  heap block body */
  234.  
  235. # define BODY_SZ ((HBLKSIZE-sizeof(struct hblkhdr))/sizeof(word))
  236.  
  237. struct hblk {
  238.     struct hblkhdr hb_hdr;
  239.     word hb_body[BODY_SZ];
  240. };
  241.  
  242. # define hb_sz hb_hdr.hbh_sz
  243. # define hb_index hb_hdr.hbh_index
  244. # define hb_marks hb_hdr.hbh_marks
  245. # define hb_next hb_hdr.hbh_next
  246. # define hb_uninit hb_hdr.hbh_marks[0]
  247. # define hb_mask hb_hdr.hbh_mask
  248.  
  249. /*  lists of all heap blocks and free lists  */
  250. /* Primary declaration is in alloc.c         */
  251. /* These are grouped together in s struct    */
  252. /* so that they can be easily skipped by the */
  253. /* mark routine.                             */
  254. /* misc.c knows about their relative order.  */
  255.  
  256. struct __gc_arrays {
  257.   struct obj * _aobjfreelist[MAXAOBJSZ+1];         /* free list for atomic objs*/
  258.   struct obj * _objfreelist[MAXOBJSZ+1];           /* free list for objects */
  259.   struct hblk * _hblklist[MAXHBLKS];
  260. };
  261.  
  262. extern struct __gc_arrays _gc_arrays; 
  263.  
  264. # define objfreelist _gc_arrays._objfreelist
  265. # define aobjfreelist _gc_arrays._aobjfreelist
  266. # define hblklist _gc_arrays._hblklist
  267.  
  268. # define begin_gc_arrays ((char *)(&_gc_arrays))
  269. # define end_gc_arrays (((char *)(&_gc_arrays)) + (sizeof _gc_arrays))
  270.  
  271. struct hblk ** last_hblk;  /* Pointer to one past the real end of hblklist */
  272.  
  273. struct hblk * hblkfreelist;
  274.  
  275. extern long heapsize;       /* Heap size in bytes */
  276.  
  277. # define HINCR 16          /* Initial heap increment, in blocks              */
  278. long hincr;                /* current heap increment, in blocks              */
  279.  
  280. /* Operations */
  281. # define update_hincr  hincr = (hincr * HINCR_MULT)/HINCR_DIV
  282. # define HB_SIZE(p) abs((p) -> hb_sz)
  283. # define abs(x)  ((x) < 0? (-(x)) : (x))
  284.  
  285. /*  procedures */
  286.  
  287. extern void
  288. freehblk();
  289.  
  290. extern struct hblk *
  291. allochblk();
  292.  
  293. /****************************/
  294. /*                          */
  295. /*   Objects                */
  296. /*                          */
  297. /****************************/
  298.  
  299. /*  object structure */
  300.  
  301. struct obj {
  302.     union fredhead {
  303.     struct obj *oun_link;   /* --> next object in freelist */
  304. #         define obj_link       obj_un.oun_link
  305.     word oun_component[1];  /* treats obj as list of words */
  306. #         define obj_component  obj_un.oun_component
  307.     } obj_un;
  308. };
  309.  
  310. /*  Test whether something points to a legitimate heap object */
  311.  
  312.  
  313. extern char end;
  314.  
  315. char * heaplim;  /* 1 + last address in heap */
  316.  
  317. char * startup_sfp; /* Frame pointer for Russell startup routine */
  318.  
  319. /* Check whether the given HBLKSIZE aligned hblk pointer refers to a     */
  320. /* legitimate chunk.                                                     */
  321. /* Assumes that *p is addressable                                        */
  322. #define is_hblk(p) ( (p) -> hb_index >= hblklist \
  323.              && (p) -> hb_index < last_hblk \
  324.              && *((p)->hb_index) == (p))
  325.  
  326. /* Check whether q points to an object inside hblk p for objects of size s */
  327. /* with mask m corresponding to s.                                         */
  328. /* Assumes q-p and s << 2 each fit into a short.                           */
  329. #define is_proper_obj(q,p,s,m) \
  330.         (((long)(m)) >= 0 ? \
  331.         (((((long)(q)) - (sizeof (struct hblkhdr))) & (m)) == 0) \
  332.         : (((short)(((long) (q)) - ((long)(p)) - (sizeof (struct hblkhdr)))) \
  333.            % (((short)(s)) << 2) == 0))
  334.  
  335. /* The following is a quick test whether something is an object pointer */
  336. /* It may err in the direction of identifying bogus pointers            */
  337. /* Assumes heap + text + data + bss < 64 Meg.                           */
  338. #ifdef M68K
  339. #   define POINTER_MASK 0xfc000003  /* pointer & POINTER_MASK should be 0 */
  340. #else
  341. #   ifdef VAX
  342. #     define POINTER_MASK 0xfc000003
  343. #   else
  344. #     ifdef SPARC
  345. #       define POINTER_MASK 0xfc000003
  346. #     else
  347. #       ifdef I386
  348. #         define POINTER_MASK 0xfc000003
  349. #       else
  350.        --> dont know <--
  351. #       endif
  352. #     endif
  353. #   endif
  354. #endif
  355.  
  356. #ifdef UNALIGNED
  357. #  define quicktest(p) (((long)(p)) > ((long)(&end)) \
  358.                         && !(((unsigned long)(p)) & POINTER_MASK) \
  359.                         && (((long)(p)) & HBLKMASK))
  360.         /* The last test throes out pointers to the beginning of heap */
  361.         /* blocks.  Small integers shifted by 16 bits tend to look    */
  362.         /* like these.                                                */
  363. #else
  364. #  define quicktest(p) (((long)(p)) > ((long)(&end)) \
  365.                         && !(((unsigned long)(p)) & POINTER_MASK))
  366. #endif
  367.  
  368.  
  369. /*  Marks are in a reserved area in                          */
  370. /*  each heap block.  Each word has one mark bits associated */
  371. /*  with it. Only those corresponding to the beginning of an */
  372. /*  object are used.                                         */
  373.  
  374.  
  375. /* Operations */
  376.  
  377. /*
  378.  * Retrieve, set, clear the mark bit corresponding
  379.  * to the nth word in a given heap block.
  380.  * Note that retrieval will work, so long as *hblk is addressable.
  381.  * In particular, the check whether hblk is a legitimate heap block
  382.  * can be postponed until after the mark bit is examined.
  383.  *
  384.  * (Recall that bit n corresponds to object beginning at word n)
  385.  */
  386.  
  387. # define mark_bit(hblk,n) (((hblk)->hb_marks[divWORDSZ(n)] \
  388.                 >> (modWORDSZ(n))) & 1)
  389.  
  390. /* The following assume the mark bit in question is either initially */
  391. /* cleared or it already has its final value                         */
  392. # define set_mark_bit(hblk,n) (hblk)->hb_marks[divWORDSZ(n)] \
  393.                 |= 1 << modWORDSZ(n)
  394.  
  395. # define clear_mark_bit(hblk,n) (hblk)->hb_marks[divWORDSZ(n)] \
  396.                 &= ~(1 << modWORDSZ(n))
  397.  
  398. /*  procedures */
  399.  
  400. /* Small object allocation routines */
  401. extern struct obj * allocobj();
  402. extern struct obj * allocaobj();
  403.  
  404. /* general purpose allocation routines */
  405. extern struct obj * ralloc();
  406.  
  407. extern struct obj * ralloc_comp();
  408.  
  409.